#include "stdlib.h"


#define STACK_INIT_SIZE  100
#define STACK_INCRMENT_SIZE  10


typedef int ElemType;
typedef struct{
    //连续内存首地址
    ElemType *base;
    //栈顶指针（这里指定为指向将要添加元素的位置）
    ElemType *top;
    //元素个数
    int size;
}Sqtack;

/**
 * @brief init stack
 * 
 * @param s stack
 */
void init(Sqtack &s){
    //申请内存
    s.base = (ElemType *) malloc(STACK_INIT_SIZE * sizeof(ElemType));
    //内存分配失败
    if(!s.base){
        exit(-1);
    }
    s.size = STACK_INIT_SIZE;
    //top初始指向栈底，表示空栈
    s.top = s.base;
}

/**
 * @brief Get the Top element of stack
 * 
 * @param s stack
 * @param e stored value
 */
void getTop(Sqtack &s, ElemType &e){
    if(s.base == s.top){    //空栈
        return;
    }
    e = *(s.top-1);
}

/**
 * @brief add a element to the top of stack 
 * 
 * @param s stack
 * @param e element
 */
void push(Sqtack &s, ElemType e){
    //内存不足
    if(s.top - s.base == s.size){
        s.base = (ElemType *) realloc(s.base, (s.size + STACK_INCRMENT_SIZE) * sizeof(ElemType));
        if(!s.base){
            exit(-1);
        }
        s.top = s.base + s.size;
        s.size += STACK_INCRMENT_SIZE;
    }
    *(s.top++) = e;
}

/**
 * @brief remove a element from the top of stack
 * 
 * @param s stack
 * @param e element
 */
void pop(Sqtack &s, ElemType &e){
    //空栈
    if(s.top == s.base){
        return;
    }
    e = * (--s.top);
}